Bước thăng tiến sự nghiệp nhanh chóng của Lelyushenko một phần là do cuộc thanh trừng của quân đội Liên Xô trước đây tạo ra một môi trường cơ hội, nhưng chủ yếu cũng do danh tiếng mà ông đạt được ở Phần Lan, nơi ông đã phát triển các chiến thuật hợp tác bộ binh thành công. Mùa xuân năm 1941, Lelyushenko giữ quân hàm thiếu tướng và được chỉ định làm tư lệnh Quân đoàn cơ giới 21, đóng tại quân khu Moskva. Khi đó, biên chế một quân đoàn cơ giới của Liên Xô bao gồm 2 sư đoàn xe tăng và 1 sư đoàn súng trường cơ giới. Lực lượng xe tăng chủ lực là loại BT7 và T26; các mẫu T34 và KV-1 mới sau này đã gây cho quân Đức rất nhiều rắc rối, khi đó vận chưa sẵn sàng về số lượng.

Ngày 23 tháng 6 năm 1941, một ngày sau khi Đức tiến hành Chiến dịch Barbarossa, Lelyushenko bắt đầu tổ chức lại bộ chỉ huy của mình để chống lại các mối đe dọa cụ thể do cuộc xâm lược của Đức. Thương vong bắt đầu gia tăng khi máy bay Đức đánh phá các khu vực tập kết phân tán của đơn vị.

Lelyushenko bắt đầu cuộc chiến của mình bằng một cuộc tấn công tại Daugavpils vào ngày 28 tháng 6, nơi Quân đoàn của ông tấn công mạnh vào Quân đoàn thiết giáp 56. Điều này đã được ghi nhận bởi tướng von Manstein, trong cuốn sách "Những ký ức đã mất", nơi ông mô tả vị thế của quân Đức liên tục trở nên "khá nghiêm trọng" trước khi họ có thể giành lại quyền kiểm soát.

Tuy nhiên, nhìn chung, quân đội Liên Xô gặp nhiều khó khăn. Chính vì vậy, những chỉ huy có tính cách mạnh mẽ như Lelyushenko mới tỏa sáng trong khi tình chiến trường thay đổi liên tục. Được bổ sung vào Phương diện quân Tây Bắc, Lelyushenko sau đó được nhận Huân chương Sao đỏ vì sự phòng thủ ngoan cường của đơn vị khi lực lượng Liên Xô bị đánh lui 450 km trong 18 ngày.

Vào tháng 8, Lelyushenko được Stalin triệu tập và giao nhiệm vụ thành lập 22 lữ đoàn xe tăng - một đội hình biên chế mới - được trang bị xe tăng T34 và KV1. Trên cương vị này, ông đã chỉ huy nhiều 'ngôi sao' của lực lượng thiết giáp Liên Xô trong tương lai, chẳng hạn như Rotmistrov, Katukov, Solomatin. Tất cả đều là chỉ huy lữ đoàn dưới quyền Lelyushenko.